/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-11 17:48:49
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-11 20:21:27
 * @FilePath: \LeetCode\53.最大子数组和.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子数组和
 *
 * 方法1：子数组和 = 前缀和 perfix_sum 之差
 * - 使用 max_perfix_sum - min_perfix_sum 造成逻辑混乱，只用 min_perfix_sum 即可
 * 
 * 方法2：动态规划算法
 * - 状态 dp[i]: 以 i 号元素结尾的最大字段和
   dp[0] = (val<0) ? 0 : val
   dp[1] = arr[1] + dp[0]
   dp[2] = arr[2] + dp[1]
 * - 状态转移方程：dp[i] = max{arr[i] + dp[i-1], arr[i]}  i > 0
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int maxSubArray_01(std::vector<int> &nums)
    {
        int max_subsum = std::numeric_limits<int>::min();
        int perfix_sum = 0;
        int min_perfix_sum = 0; // perfix_sum 之前的最小子数组和
        
        for (auto n : nums)
        {
            perfix_sum += n;
            max_subsum = std::max(max_subsum, (perfix_sum - min_perfix_sum));
            min_perfix_sum = std::min(perfix_sum, min_perfix_sum);
        }

        return max_subsum;
    }

    int maxSubArray_02(std::vector<int> &nums)
    {
        int perfix_sum = 0;
        int max_subsum = nums[0];

        for(const auto& n : nums)
        {
            perfix_sum = std::max((perfix_sum + n), n);
            max_subsum = std::max(max_subsum, perfix_sum);
        }

        return max_subsum;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {1, 2, -2, 0, -1};
    // std::cout << solution.maxSubArray(nums) << std::endl;
    return 0;
}